#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2019/5/13 17:56
# @USER    : Connor
# @File    : RegularExpressionMatching.py
# @Software: PyCharm
# @Version  : Python-3.6
# @TASK:

"""
- String
- Dynamic Programming
- Recursion
"""


class Solution:
    """
    Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
        - '.' Matches any single character.
        - '*' Matches zero or more of the preceding element.

    The matching should cover the entire input string (not partial).


    Note:
        s could be empty and contains only lowercase letters a-z.
        p could be empty and contains only lowercase letters a-z, and characters like . or *.

    Example 1:
        Input:
            s = "aa"

            p = "a"

        Output: false

        Explanation: "a" does not match the entire string "aa".

    Example 2:
        Input:
            s = "aa"

            p = "a*"

        Output: true

        Explanation: '*' means zero or more of the precedeng element, 'a'.
        Therefore, by repeating 'a' once, it becomes "aa".

    Example 3:
        Input:
            s = "ab"

            p = ".*"

        Output: true

        Explanation: ".*" means "zero or more (*) of any character (.)".

    Example 4:
        Input:
            s = "aab"

            p = "c*a*b"

        Output: true

        Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

    Example 5:
        Input:
            s = "mississippi"

            p = "mis*is*p*."

        Output: false
    """

    def isMatch(self, s: str, p: str) -> bool:
        """
        Args:
            s (str):
            p (str):

        Returns:
            bool
        """

        if not p:
            return not s

        first_m = bool(s) and p[0] in {s[0], '.'}

        if len(p) >= 2 and p[1] == '*':
            return self.isMatch(s, p[2:]) or first_m and self.isMatch(s[1:], p)
        else:
            return first_m and self.isMatch(s[1:], p[1:])

    def isMatch_dp(self, s: str, p: str) -> bool:
        memo = {}

        def dp(i, j):
            if (i, j) not in memo:
                if j == len(p):
                    ans = i == len(s)
                else:
                    first_match = i < len(s) and p[j] in {s[i], '.'}
                    if j + 1 < len(p) and p[j + 1] == '*':
                        ans = dp(i, j + 2) or first_match and dp(i + 1, j)
                    else:
                        ans = first_match and dp(i + 1, j + 1)

                memo[i, j] = ans
            return memo[i, j]

        return dp(0, 0)


if __name__ == '__main__':
    S = Solution()
    sample = 'mississippi'
    psample = 'mis*is*p*.'
    print(S.isMatch(sample, psample))
    print(S.isMatch_dp(sample, psample))
    print('done')
